#include <bits/stdc++.h>

using namespace std;

// class MyLinkedList
// {
// public:
//     MyLinkedList()
//     {
//     }

//     int get(int index)
//     {
//         if (index < vec.size())
//         {
//             return *(vec.begin() + index);
//         }
//         else
//         {
//             return -1;
//         }
//     }

//     void addAtHead(int val)
//     {
//         vec.insert(vec.begin(), val);
//     }

//     void addAtTail(int val)
//     {
//         vec.push_back(val);
//     }

//     void addAtIndex(int index, int val)
//     {
//         int length = vec.size();
//         if (index < length)
//         {
//             vec.insert(vec.begin() + index, val);
//         }
//         else if (index == length)
//         {
//             vec.push_back(val);
//         }
//     }

//     void deleteAtIndex(int index)
//     {
//         if (index < vec.size())
//         {
//             vec.erase(vec.begin() + index);
//         }
//     }

// private:
//     vector<int> vec;
// };

class MyLinkedList
{
public:
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };

    MyLinkedList()
    {
        dummy_head = new ListNode(0);
        size = 0;
    }

    int get(int index)
    {
        if (index >= size)
        {
            return -1;
        }
        ListNode *cur = dummy_head;
        while (index != 0)
        {
            index--;
            cur = cur->next;
        }
        return cur->next->val;
    }

    void addAtHead(int val)
    {
        ListNode *node = new ListNode(val);
        node->next = dummy_head->next;
        dummy_head->next = node;
        size++;
    }

    void addAtTail(int val)
    {
        ListNode *node = new ListNode(val);
        ListNode *cur = dummy_head;
        while (cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = node;
        size++;
    }

    void addAtIndex(int index, int val)
    {
        if (index > size)
        {
            return;
        }
        ListNode *node = new ListNode(val);
        ListNode *cur = dummy_head;
        while (index != 0)
        {
            index--;
            cur = cur->next;
        }
        node->next = cur->next;
        cur->next = node;
        size++;
    }

    void deleteAtIndex(int index)
    {
        if (index >= size)
        {
            return;
        }
        ListNode *cur = dummy_head;
        while (index != 0)
        {
            index--;
            cur = cur->next;
        }
        ListNode *tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        size--;
    }

    void printf_list()
    {
        ListNode *cur = dummy_head;
        while (cur->next != nullptr)
        {
            printf("%d ", cur->next->val);
            cur = cur->next;
        }
        printf("\n");
    }

private:
    ListNode *dummy_head;
    int size;
};

int main()
{
    MyLinkedList myLinkedList;
    myLinkedList.addAtHead(1);
    myLinkedList.printf_list();
    myLinkedList.addAtTail(3);
    myLinkedList.printf_list();
    myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
    myLinkedList.printf_list();
    myLinkedList.get(1); // 返回 2
    myLinkedList.printf_list();
    myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
    myLinkedList.printf_list();
    myLinkedList.get(1);
    return 0;
}